// https://leetcode.cn/problems/copy-list-with-random-pointer/

// 题干：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
//      构造这个链表的 深拷贝， 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
//      新节点的 next 指针和 random 指针也都应指向复制链表中的新节点
//      并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点

// 示例：输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
//      输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

// 碎语：怎么构造映射关系？用map!

#include <iostream>
using namespace std;

#include <map>

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution
{
public:
    Node* copyRandomList(Node* head)
    {
        map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr, * copytail = nullptr;

        Node* cur = head;
        while (cur)
        {
            if (copyhead == nullptr) {
                copyhead = copytail = new Node(cur->val);
            }
            else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }

            // key为旧，value为新节点
            nodeMap[cur] = copytail;
            cur = cur->next;
        }

        cur = head;
        while (cur)
        {
            nodeMap[cur]->random = nodeMap[cur->random];
            cur = cur->next;
        }

        return copyhead;
    }
};



